{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Reverse Pairs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #binary-indexed-tree #segment-tree #array #binary-search #divide-and-conquer #ordered-set #merge-sort"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树状数组 #线段树 #数组 #二分查找 #分治 #有序集合 #归并排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: reversePairs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #翻转对"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个数组&nbsp;<code>nums</code>&nbsp;，如果&nbsp;<code>i &lt; j</code>&nbsp;且&nbsp;<code>nums[i] &gt; 2*nums[j]</code>&nbsp;我们就将&nbsp;<code>(i, j)</code>&nbsp;称作一个<strong><em>重要翻转对</em></strong>。</p>\n",
    "\n",
    "<p>你需要返回给定数组中的重要翻转对的数量。</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入</strong>: [1,3,2,3,1]\n",
    "<strong>输出</strong>: 2\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入</strong>: [2,4,3,5,1]\n",
    "<strong>输出</strong>: 3\n",
    "</pre>\n",
    "\n",
    "<p><strong>注意:</strong></p>\n",
    "\n",
    "<ol>\n",
    "\t<li>给定数组的长度不会超过<code>50000</code>。</li>\n",
    "\t<li>输入数组中的所有数字都在32位整数的表示范围内。</li>\n",
    "</ol>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [reverse-pairs](https://leetcode.cn/problems/reverse-pairs/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [reverse-pairs](https://leetcode.cn/problems/reverse-pairs/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,3,2,3,1]', '[2,4,3,5,1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reversePairs(self, nums: List[int]) -> int:\n",
    "        def merge_sort(left, right):\n",
    "            if left >= right:\n",
    "                return 0\n",
    "            mid = (left + right)//2\n",
    "            count = merge_sort(left, mid) + merge_sort(mid + 1, right)\n",
    "\n",
    "            # Count the number of reverse pairs between two sorted halves\n",
    "            i, j = left, mid+1\n",
    "            while i <= mid and j<= right:\n",
    "                if nums[i]> 2*nums[j]:\n",
    "                    count+=mid-i+1\n",
    "                    j+=1\n",
    "                else:\n",
    "                    i+=1\n",
    "            \n",
    "            nums[left:right + 1] = sorted(nums[left:right + 1])\n",
    "            return count\n",
    "        return merge_sort(0, len(nums)-1)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    \n",
    "    def __init__(self):\n",
    "        self.count = 0\n",
    "        \n",
    "    def reversePairs(self, nums):\n",
    "        \n",
    "        def divide(lst):\n",
    "           \n",
    "            L = len(lst)\n",
    "            if L <= 1:                          \n",
    "                return lst\n",
    "            else:                               \n",
    "                return merger(divide(lst[:int(L/2)]), divide(lst[int(L/2):]))\n",
    "            \n",
    "        def merger(left, right):\n",
    "            i, j = 0, 0                         \n",
    "            while i < len(left) and j < len(right):\n",
    "                if left[i] <= 2*right[j]:\n",
    "                    i += 1\n",
    "                else:\n",
    "                    self.count += len(left)-i    \n",
    "                    j += 1\n",
    "            return sorted(left+right)\n",
    "        \n",
    "        divide(nums)\n",
    "        return self.count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reversePairs(self, nums: List[int]) -> int:\n",
    "        self.res = 0\n",
    "        self.mergeSort(nums)\n",
    "        return self.res\n",
    "    \n",
    "    def mergeSort(self, nums):\n",
    "        if len(nums) <= 1:\n",
    "            return nums\n",
    "        n = len(nums)\n",
    "        mid = int(n/2)\n",
    "        return self.mergeTwo(self.mergeSort(nums[:mid]), self.mergeSort(nums[mid:]))\n",
    "    \n",
    "    def mergeTwo(self, sa, sb):\n",
    "        na = len(sa)\n",
    "        nb = len(sb)\n",
    "        i = 0\n",
    "        j = 0\n",
    "        while i < na and j < nb:\n",
    "            if sa[i] > 2*sb[j]:\n",
    "                self.res += na - i\n",
    "                j += 1\n",
    "            else:\n",
    "                i += 1\n",
    "\n",
    "        \n",
    "        #return sorted(sa+sb)\n",
    "        \n",
    "        res = sa + sb\n",
    "        i = 0\n",
    "        j = 0\n",
    "        k = 0\n",
    "        while i < na and j < nb:\n",
    "            if sa[i] <= sb[j]:\n",
    "                res[k] = sa[i]\n",
    "                i += 1\n",
    "                \n",
    "            else:\n",
    "                res[k] = sb[j]\n",
    "                j += 1\n",
    "            k += 1\n",
    "        while i < na:\n",
    "            res[k] = sa[i]\n",
    "            i += 1\n",
    "            k += 1\n",
    "        while j < nb:\n",
    "            res[k] = sb[j]\n",
    "            j += 1\n",
    "            k += 1\n",
    "        return res\n",
    "        \"\"\"\n",
    "        for k in range(len(res)):\n",
    "            if i >= na:\n",
    "                res[k] = sb[j]\n",
    "                j += 1\n",
    "                continue\n",
    "            if j >= nb:\n",
    "                res[k] = sa[i]\n",
    "                i += 1\n",
    "                continue\n",
    "            \n",
    "            if sa[i] <= sb[j]:\n",
    "                res[k] = sa[i]\n",
    "                i += 1\n",
    "            else:\n",
    "                res[k] = sb[j]\n",
    "                j += 1\n",
    "        \n",
    "        return res\n",
    "        \"\"\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reversePairs(self, nums: List[int]) -> int:\n",
    "        ans, sorted_nums = 0, []\n",
    "        while nums:\n",
    "            num = nums.pop()\n",
    "            idx1 = self.get_idx(sorted_nums, num)\n",
    "            idx2 = self.get_idx(sorted_nums, num*2)\n",
    "            ans += idx1\n",
    "            sorted_nums.insert(idx2, num*2)\n",
    "        return ans\n",
    "\n",
    "    def get_idx(self, sorted_nums, num) -> int:\n",
    "        if not sorted_nums:\n",
    "            return 0\n",
    "        left, right = 0, len(sorted_nums) - 1\n",
    "        while left < right:\n",
    "            mid = left + ((right-left) >> 1)\n",
    "            if sorted_nums[mid] >= num:\n",
    "                right = mid\n",
    "            else:\n",
    "                left = mid + 1\n",
    "        return left + 1 if sorted_nums[left] < num else left"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reversePairs(self, nums: List[int]) -> int:\n",
    "        tb, res = [], 0\n",
    "        for n in reversed(nums) :\n",
    "            res += bisect.bisect_left(tb, n)\n",
    "            n2 = 2*n\n",
    "            idx = bisect.bisect_left(tb, n2)\n",
    "            tb.insert(idx, n2)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def reversePairs(self, nums):\n",
    "        self.cnt = 0\n",
    "        def mergeSort(lst):\n",
    "            L = len(lst)\n",
    "            if L <= 1:\n",
    "                return lst\n",
    "            else:\n",
    "                return mergeTwo(mergeSort(lst[:L//2]), mergeSort(lst[L//2:]))\n",
    "        def mergeTwo(left, right):\n",
    "            l, r = 0, 0\n",
    "            while l < len(left) and r < len(right):\n",
    "                if left[l] <= 2 * right[r]:\n",
    "                    l += 1\n",
    "                else:\n",
    "                    self.cnt += len(left) - l\n",
    "                    r += 1\n",
    "            return sorted(left+right)\n",
    "\n",
    "        mergeSort(nums)\n",
    "        return self.cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 抄的 需要重新写\n",
    "class Solution:\n",
    "    def reversePairs(self, nums: List[int]) -> int:\n",
    "        self.cnt = 0\n",
    "        self.mergesort(nums,0,len(nums)-1)\n",
    "        return self.cnt\n",
    "        \n",
    "    def mergesort(self,nums,L,R):\n",
    "        if L<R:#否则死循环\n",
    "            m = (L+R)//2\n",
    "            self.mergesort(nums,L,m)\n",
    "            self.mergesort(nums,m+1,R)\n",
    "            self.merge(nums,L,m,R)\n",
    "    \n",
    "    def merge(self,nums,L,m,R):\n",
    "        p1 = L\n",
    "        p2 = m+1\n",
    "        temp = []\n",
    "        while p1<=m and p2<=R:\n",
    "            if nums[p1]<=nums[p2]:\n",
    "                temp.append(nums[p1])\n",
    "                p1+=1\n",
    "            else:\n",
    "                temp.append(nums[p2])\n",
    "                p2+=1\n",
    "        ############################\n",
    "        ii, jj = L, m + 1\n",
    "        while ii <= m and jj <= R:\n",
    "            if nums[ii] <= 2 * nums[jj]:\n",
    "                ii += 1\n",
    "            else:\n",
    "                self.cnt += (m - ii + 1)\n",
    "                jj += 1\n",
    "        ############################\n",
    "        if p1<=m:#等号\n",
    "            temp+=nums[p1:m+1]\n",
    "        if p2<=R:#等号\n",
    "            temp+=nums[p2:R+1]\n",
    "        # print(L,R,len(temp))\n",
    "        for i in range(len(temp)):\n",
    "            nums[L + i] = temp[i]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def reversePairs(self, nums: List[int]) -> int:\r\n",
    "        def count(nums,left,right):\r\n",
    "            if left >= right:\r\n",
    "                return 0\r\n",
    "            mid = (left + right) >> 1\r\n",
    "            r = count(nums,left,mid) + count(nums,mid + 1,right)\r\n",
    "            temp = [None] * (right - left + 1)\r\n",
    "            i = left\r\n",
    "            j = mid + 1\r\n",
    "            t = j\r\n",
    "            for k in range(len(temp)):\r\n",
    "                if i <= mid and (j > right or nums[i] < nums[j]):\r\n",
    "                    while t <= right and nums[i] > 2 * nums[t]:\r\n",
    "                        t += 1\r\n",
    "                    r += t - mid - 1\r\n",
    "                    temp[k] = nums[i]\r\n",
    "                    i += 1\r\n",
    "                else:\r\n",
    "                    temp[k] = nums[j]\r\n",
    "                    j += 1\r\n",
    "            for x in range(len(temp)):\r\n",
    "                nums[left + x] = temp[x]\r\n",
    "            return r                 \r\n",
    "        ans = count(nums,0,len(nums) - 1)\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reversePairs(self, nums: List[int]) -> int:\n",
    "        return self.reversePairsRecursive(nums, 0, len(nums)-1)\n",
    "\n",
    "    def reversePairsRecursive(self, nums, left, right):\n",
    "        if left == right: return 0\n",
    "        mid = (left + right) // 2\n",
    "        n1 = self.reversePairsRecursive(nums, left, mid)\n",
    "        n2 = self.reversePairsRecursive(nums, mid+1, right)\n",
    "        ret = n1 + n2\n",
    "\n",
    "        i, j = left, mid+1\n",
    "        while i <= mid:\n",
    "            while j <= right and nums[i] > 2 * nums[j]: j+=1\n",
    "            ret += j - mid - 1\n",
    "            i += 1\n",
    "        temp = [0] * (right-left+1)\n",
    "        p1, p2, p = left, mid + 1, 0\n",
    "        while p1 <= mid and p2 <= right:\n",
    "            if nums[p1] <= nums[p2]:\n",
    "                temp[p] = nums[p1]\n",
    "                p1 += 1\n",
    "                p += 1\n",
    "            else:\n",
    "                temp[p] = nums[p2]\n",
    "                p2 += 1\n",
    "                p += 1\n",
    "        while p1 <= mid:\n",
    "            temp[p] = nums[p1]\n",
    "            p1 += 1\n",
    "            p += 1\n",
    "        while p2 <= right:\n",
    "            temp[p] = nums[p2]\n",
    "            p2 += 1\n",
    "            p += 1\n",
    "        for i in range(len(temp)):\n",
    "            nums[left + i] = temp[i]\n",
    "        return ret\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def merge_sort(self, nums: List[int], lo: int, hi: int, tmp: List[int]):\n",
    "        if lo >= hi:\n",
    "            return 0\n",
    "        mid = lo + (hi - lo) // 2\n",
    "        left_count = self.merge_sort(nums, lo, mid, tmp)\n",
    "        right_count = self.merge_sort(nums, mid + 1, hi, tmp)\n",
    "\n",
    "        count = 0\n",
    "        i = lo\n",
    "        j = mid + 1\n",
    "        while j <= hi:\n",
    "            \"\"\"\n",
    "            1   4   7   8       2   5   8   10\n",
    "                    i           j\n",
    "            \"\"\"\n",
    "            while i <= mid and nums[i] <= 2 * nums[j]:\n",
    "                i += 1\n",
    "            count += mid - i + 1\n",
    "            j += 1\n",
    "\n",
    "        for i in range(lo, hi + 1):\n",
    "            tmp[i] = nums[i]\n",
    "\n",
    "        l = lo\n",
    "        r = mid + 1\n",
    "        for k in range(lo, hi + 1):\n",
    "            if l == mid + 1:\n",
    "                nums[k] = tmp[r]\n",
    "                r += 1\n",
    "            elif r == hi + 1:\n",
    "                nums[k] = tmp[l]\n",
    "                l += 1\n",
    "            elif tmp[l] <= tmp[r]:\n",
    "                nums[k] = tmp[l]\n",
    "                l += 1\n",
    "            else:\n",
    "                nums[k] = tmp[r]\n",
    "                r += 1\n",
    "\n",
    "        return count + left_count + right_count\n",
    "\n",
    "    def reversePairs(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        count = self.merge_sort(nums, 0, n - 1, [0] * n)\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# #把输入数组反过来,乘以2然后插入一个有序数组中，插入的位置就是在原数组中位于它右侧且小于它的1/2的元素的个数。\n",
    "# class Solution:\n",
    "#     def reversePairs(self, nums: List[int]) -> int:\n",
    "#         tb, res = [], 0\n",
    "#         for n in nums[::-1] :\n",
    "#             res += bisect.bisect_left(tb, n)\n",
    "#             n2 = 2*n\n",
    "#             idx = bisect.bisect_left(tb, n2)\n",
    "#             tb.insert(idx, n2)\n",
    "#         return res\n",
    "\n",
    "# 反向思考：对于 nums 中的每一项 num，我们找前面出现过的大于 num * 2 的数。\n",
    "# 构造有序序列 d，然后在 d 上做二分。\n",
    "# 构建 d ：将 nums 中已经遍历过的数字全部放到 d 中即可。\n",
    "class Solution:\n",
    "    def reversePairs(self, A):\n",
    "        d = []\n",
    "        ans = 0\n",
    "\n",
    "        for a in A:\n",
    "            i = bisect.bisect_right(d, a * 2)\n",
    "            ans += len(d) - i\n",
    "            bisect.insort(d, a)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reversePairs(self, nums: List[int]) -> int:\n",
    "        size = len(nums)\n",
    "        if size <= 1:\n",
    "            return 0\n",
    "        temp = [0 for _ in range(size)]\n",
    "        res = self.reverse_paris(nums, 0, size - 1, temp)\n",
    "        return res\n",
    "\n",
    "    def merge_two_sorted_array(self, nums, left, mid, right, temp):\n",
    "        for i in range(left, right + 1):\n",
    "            temp[i] = nums[i]\n",
    "        a = left\n",
    "        b = mid + 1\n",
    "        count = 0\n",
    "        while a <= mid and b <= right:\n",
    "            if nums[a] > 2 * nums[b]:\n",
    "                b += 1\n",
    "                count += mid - a + 1\n",
    "            else:\n",
    "                a += 1\n",
    "        a = left\n",
    "        b = mid + 1\n",
    "        for i in range(left, right + 1):\n",
    "            if a >= mid + 1:\n",
    "                nums[i] = temp[b]\n",
    "                b += 1\n",
    "            elif b >= right + 1:\n",
    "                nums[i] = temp[a]\n",
    "                a += 1\n",
    "            elif temp[a] >= temp[b]:\n",
    "                nums[i] = temp[b]\n",
    "                b += 1\n",
    "            else:\n",
    "                nums[i] = temp[a]\n",
    "                a += 1\n",
    "        return count\n",
    "\n",
    "\n",
    "    def reverse_paris(self, nums, left, right, temp):\n",
    "        if left == right:\n",
    "            return 0\n",
    "        mid = (left + right) // 2\n",
    "        left_num = self.reverse_paris(nums, left, mid, temp)\n",
    "        right_num = self.reverse_paris(nums, mid + 1, right, temp)\n",
    "        # if nums[indexes[mid]] <= nums[indexes[mid + 1]]:\n",
    "        #     return\n",
    "        merge_num = self.merge_two_sorted_array(nums, left, mid, right, temp)\n",
    "        return left_num + right_num + merge_num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reversePairs(self, nums: List[int]) -> int:\n",
    "        self.ans = 0\n",
    "        self.mergeSort(nums, 0, len(nums)-1)\n",
    "        return self.ans\n",
    "\n",
    "    def mergeSort(self, nums, left, right):\n",
    "        if left >= right:\n",
    "            return 0\n",
    "        mid = left + right >> 1\n",
    "        self.mergeSort(nums, left, mid)\n",
    "        self.mergeSort(nums, mid+1, right)\n",
    "        self.calc(nums, left, right, mid)\n",
    "        self.merge(nums, left, right, mid)\n",
    "\n",
    "    def calc(self, nums, left, right, mid):\n",
    "        # 左边[left, mid]，右边[mid + 1, right]\n",
    "        if left >= right:\n",
    "            return 0\n",
    "        j = mid\n",
    "        for i in range(left, mid+1):\n",
    "            while j < right and nums[i] > 2 * nums[j+1]:\n",
    "                j += 1    \n",
    "            self.ans += j - mid  # 因为 [mid+1, right]已经有序：[mid+1, ... j, ... right], j 和 mid+1中间一共有 j-mid个数\n",
    "\n",
    "    def merge(self, nums, left, right, mid):\n",
    "        if left > right:\n",
    "            return\n",
    "        tmp = []\n",
    "        i = left\n",
    "        j = mid + 1\n",
    "        while i <= mid and j <= right:\n",
    "            if nums[i] <= nums[j]:\n",
    "                tmp.append(nums[i])\n",
    "                i += 1\n",
    "            if nums[i] > nums[j]:\n",
    "                tmp.append(nums[j])\n",
    "                j += 1\n",
    "        if i <= mid:\n",
    "            while i <= mid:\n",
    "                tmp.append(nums[i])\n",
    "                i += 1\n",
    "        if j <= right:\n",
    "            while j <= right:\n",
    "                tmp.append(nums[j])\n",
    "                j += 1\n",
    "        nums[left: right+1] = tmp\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def reversePairs(self, nums: List[int]) -> int:\n",
    "        sl = SortedList()\n",
    "        sl.add(nums[0])\n",
    "        res = 0\n",
    "        for i in range(1,len(nums)):\n",
    "            res += i - sl.bisect_left(nums[i]*2 + 1)\n",
    "            sl.add(nums[i])\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def reversePairs(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        sl = SortedList()\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            ans += sl.bisect_left(nums[i])\n",
    "            sl.add(2 * nums[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def reversePairs(self, nums: List[int]) -> int:\n",
    "        # SortedList做法：从末尾挨个把元素加进去。 O(nlogn)\n",
    "        sl = SortedList()\n",
    "        ans = 0\n",
    "        for num in nums[::-1]:\n",
    "            ans += sl.bisect_left(num)\n",
    "            sl.add(num * 2)\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from bisect import bisect_left, bisect_right\n",
    "\n",
    "class Solution:\n",
    "    def reversePairs(self, nums: List[int]) -> int:\n",
    "      b = sorted(set(nums))\n",
    "      n = len(b)\n",
    "      bit = BinaryIndexedTree(n)\n",
    "      ans = 0\n",
    "      for x in nums:\n",
    "        l = bisect_right(b, 2 * x) + 1\n",
    "        if l <= n: ans += bit.query_range(l, n)\n",
    "        bit.add(bisect_left(b, x) + 1, 1)\n",
    "      return ans\n",
    "\n",
    "class BinaryIndexedTree:\n",
    "  def __init__(self, n) -> None:\n",
    "    # 数组下标1开始为有效值\n",
    "    self.tree = [0] * (n + 1)\n",
    "  # 第i（从1开始）位加上x\n",
    "  def add(self, i, x):\n",
    "    while i < len(self.tree):\n",
    "      self.tree[i] += x\n",
    "      i += i & -i\n",
    "  # [1, i] 区间和\n",
    "  def query(self, i):\n",
    "    ans = 0\n",
    "    while i > 0:\n",
    "      ans += self.tree[i]\n",
    "      i -= i & -i\n",
    "    return ans\n",
    "  # [l, r]区间和\n",
    "  def query_range(self, l, r):\n",
    "    return self.query(r) - self.query(l - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reversePairs(self, nums: List[int]) -> int:\n",
    "        arr = nums\n",
    "        temp_arr = [0 for _ in range(len(nums))]\n",
    "        self.count = 0\n",
    "        def merge(arr, left, mid, right):\n",
    "            for idx in range(left, right + 1):\n",
    "                temp_arr[idx] = arr[idx]\n",
    "            end = mid + 1\n",
    "            for i in range(left, mid + 1):\n",
    "                while end <= right and temp_arr[i] > 2 * temp_arr[end]:\n",
    "                    end += 1\n",
    "                self.count += end - mid - 1\n",
    "            \n",
    "            i = left\n",
    "            j = mid + 1\n",
    "            for p in range(left, right + 1):\n",
    "                if i == mid + 1:\n",
    "                    arr[p] = temp_arr[j]\n",
    "                    j += 1\n",
    "                elif j == right + 1:\n",
    "                    arr[p] = temp_arr[i]\n",
    "                    i += 1\n",
    "                elif temp_arr[i] <= temp_arr[j]:\n",
    "                    arr[p] = temp_arr[i]\n",
    "                    i += 1\n",
    "                else:\n",
    "                    arr[p] = temp_arr[j]\n",
    "                    j += 1\n",
    "\n",
    "        def sort(arr, left, right):\n",
    "            if left == right:\n",
    "                return \n",
    "            mid = left + (right - left) // 2\n",
    "            sort(arr, left, mid)\n",
    "            sort(arr, mid + 1, right)\n",
    "            merge(arr, left, mid, right)\n",
    "\n",
    "        left, right = 0, len(arr) - 1\n",
    "        sort(arr, left, right)\n",
    "        return self.count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reversePairs(self, nums: List[int]) -> int:\n",
    "        self.res = 0\n",
    "        temp = [[0,0] for _ in range(len(nums))]\n",
    "        self.mergesort(nums, 0, len(nums)-1, temp)\n",
    "        return self.res\n",
    "\n",
    "    def mergesort(self, nums, start, end, temp):\n",
    "        if start==end or end == -1:\n",
    "            return\n",
    "        \n",
    "        mid = start+(end-start)//2\n",
    "        self.mergesort(nums, start, mid, temp)\n",
    "        self.mergesort(nums, mid+1, end, temp)\n",
    "        i,j = start,mid+1\n",
    "        while i <= mid and j <= end:\n",
    "            if nums[i] > 2 * nums[j]:\n",
    "                self.res += mid - i + 1\n",
    "                j+=1\n",
    "            else:\n",
    "                i+=1\n",
    "        \n",
    "        self.mergetogether(nums, start, mid, end, temp)\n",
    "\n",
    "    def mergetogether(self, nums, start, mid, end, temp):\n",
    "        i,j,k = start, mid+1, start\n",
    "        s = mid+1\n",
    "        while i<=mid and j<=end:\n",
    "            if nums[i]<=nums[j]:\n",
    "                temp[k] = nums[i]\n",
    "                k+=1\n",
    "                i+=1\n",
    "            else:\n",
    "                temp[k] = nums[j]\n",
    "                k+=1\n",
    "                j+=1\n",
    "        while i<=mid:\n",
    "            temp[k]=nums[i]\n",
    "            k+=1\n",
    "            i+=1\n",
    "        while j<=end:\n",
    "            temp[k]=nums[j]\n",
    "            k+=1\n",
    "            j+=1\n",
    "        nums[start:end+1] = temp[start:end+1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    class TreeArray:\n",
    "\n",
    "        def __init__(self,n):\n",
    "            self.nodes = [0]*n\n",
    "        \n",
    "        def add(self,index):\n",
    "            while index<len(self.nodes):\n",
    "                self.nodes[index]+=1\n",
    "                index+= index & - index\n",
    "        \n",
    "        def sumRange(self,index)->int:\n",
    "            ret = 0\n",
    "            while index:\n",
    "                ret += self.nodes[index]\n",
    "                index -= index & - index\n",
    "            return ret\n",
    "\n",
    "    def reversePairs(self, nums: List[int]) -> int:\n",
    "\n",
    "        order_list = sorted(set(nums))\n",
    "        \n",
    "        num_dict = dict()\n",
    "\n",
    "        for i in range(len(order_list)):\n",
    "            num_dict[order_list[i]] = i + 1\n",
    "        \n",
    "        cnt = len(order_list)\n",
    "\n",
    "        treeArray = Solution.TreeArray(cnt+1)\n",
    "\n",
    "        length = len(nums)\n",
    "\n",
    "        res = 0\n",
    "\n",
    "        for i in range(length-1,-1,-1):\n",
    "\n",
    "            val = nums[i]/2\n",
    "\n",
    "            if nums[i]%2 == 0:\n",
    "                val -= 1\n",
    "            \n",
    "            index = bisect.bisect_right(order_list,val)\n",
    "\n",
    "            # if index==len(order_list):\n",
    "            #     index -=1\n",
    "            # print(index)\n",
    "\n",
    "            if index>=1:\n",
    "                res += treeArray.sumRange(index)\n",
    "                \n",
    "            treeArray.add(num_dict[nums[i]])\n",
    "        \n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reversePairs(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        self.res = 0\n",
    "        nums = [(num, idx) for idx, num in enumerate(nums)]\n",
    "        \n",
    "        def mergeSort(nums, l, r):\n",
    "            if l == r:\n",
    "                return\n",
    "            mid = (l + r) // 2\n",
    "            mergeSort(nums, l, mid)\n",
    "            mergeSort(nums, mid + 1, r)\n",
    "            i, j = l, mid + 1\n",
    "            tar = mid + 1\n",
    "            temp = []\n",
    "            while i <= mid and j <= r:\n",
    "                #print(nums)\n",
    "                if nums[i][0] < nums[j][0]:\n",
    "                    temp.append(nums[i])\n",
    "                    while tar <= r and (2 * nums[tar][0] < nums[i][0]):\n",
    "                        tar += 1\n",
    "                    self.res += tar - mid - 1\n",
    "                    i += 1\n",
    "                else:\n",
    "                    temp.append(nums[j])\n",
    "                    j += 1\n",
    "            while i <= mid:\n",
    "                temp.append(nums[i])\n",
    "                while tar <= r and 2 * nums[tar][0] <nums[i][0]:\n",
    "                    tar += 1\n",
    "                self.res += tar - mid - 1\n",
    "                i += 1\n",
    "            while j <= r:\n",
    "                temp.append(nums[j])\n",
    "                j += 1\n",
    "            nums[l:r+1] = temp\n",
    "            return\n",
    "        \n",
    "        mergeSort(nums, 0, n-1)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reversePairs(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        self.tmp = [(0, 0)] * n\n",
    "        self.arr = []\n",
    "        # self.count = [0] * n\n",
    "        self.count = 0\n",
    "        for i in range(n):\n",
    "            self.arr.append((i, nums[i]))\n",
    "        self.sort_(nums, 0, n - 1)\n",
    "        return self.count\n",
    "    def sort_(self, nums, left, right):\n",
    "        if left == right:\n",
    "            return \n",
    "        mid = left + (right - left) // 2\n",
    "        self.sort_(nums, left, mid)\n",
    "        self.sort_(nums, mid + 1, right)\n",
    "        self.merge(nums, left, mid, right)\n",
    "        # print(self.arr)\n",
    "\n",
    "    def merge(self, nums, left, mid, right):\n",
    "        tmp = self.tmp\n",
    "        arr = self.arr \n",
    "        # count = self.count \n",
    "        # arr_l = [arr[i][1] for i in range(left, mid + 1)]\n",
    "        # arr_l = []\n",
    "        # for i in range(left, mid + 1):\n",
    "        #     arr_l.append(arr[i][1])\n",
    "        # for j in range(mid + 1, right + 1):\n",
    "        #     id = bisect.bisect_left(arr_l, 2 * arr[j][1])\n",
    "        #     print(arr, arr_l, arr[j][1], id)\n",
    "        #     # if id <= mid - left and  arr_l[id] > 2 * arr[j][1]: self.count += mid - left - id + 2\n",
    "        #     if id <= mid - left and  arr_l[id] > 2 * arr[j][1]: self.count += left + mid + 1 - id\n",
    "        tmp[left:right + 1] = arr[left:right + 1]\n",
    "        # 在此之后，tmp暂存了merge之前的左右两半的数组，nums[]里边的元素经过调换（merge）之后是排序好的数组\n",
    "        i = left\n",
    "        j = mid + 1\n",
    "        while i <= mid and j <= right:\n",
    "            if arr[i][1] > 2 * arr[j][1]:\n",
    "                self.count += mid - i + 1\n",
    "                j += 1\n",
    "            else:\n",
    "                i += 1\n",
    "        i = left\n",
    "        j = mid + 1\n",
    "        for p in range(left, right + 1):\n",
    "            if i == mid + 1:\n",
    "                arr[p] = tmp[j]   # 当i走到尽头的时候，把剩下的j接过来（都比i大）\n",
    "                # if tmp[i-1][1] > 2 * tmp[j][1]:   # 注意j的取值 \n",
    "                #     self.count += j - mid -1 \n",
    "                j += 1\n",
    "            elif j == right + 1:\n",
    "                arr[p] = tmp[i]\n",
    "                # if tmp[i][1] > 2 * tmp[j - 1][1]:   # 注意j的取值 \n",
    "                #     self.count += j - mid -1 \n",
    "                i += 1\n",
    "            elif tmp[i][1] <= tmp[j][1]:\n",
    "                arr[p] = tmp[i]\n",
    "                i += 1\n",
    "            elif tmp[i][1] > tmp[j][1]:\n",
    "                arr[p] = tmp[j]\n",
    "                # if tmp[i][1] > 2 * tmp[j][1]:\n",
    "                #     self.count += j - mid - 1\n",
    "                j += 1\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reversePairs(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        self.tmp = [(0, 0)] * n\n",
    "        self.arr = []\n",
    "        # self.count = [0] * n\n",
    "        self.count = 0\n",
    "        for i in range(n):\n",
    "            self.arr.append((i, nums[i]))\n",
    "        self.sort_(nums, 0, n - 1)\n",
    "        return self.count\n",
    "    def sort_(self, nums, left, right):\n",
    "        if left == right:\n",
    "            return \n",
    "        mid = left + (right - left) // 2\n",
    "        self.sort_(nums, left, mid)\n",
    "        self.sort_(nums, mid + 1, right)\n",
    "        self.merge(nums, left, mid, right)\n",
    "        # print(self.arr)\n",
    "\n",
    "    def merge(self, nums, left, mid, right):\n",
    "        tmp = self.tmp\n",
    "        arr = self.arr \n",
    "        # count = self.count \n",
    "        # arr_l = [arr[i][1] for i in range(left, mid + 1)]\n",
    "        # arr_l = []\n",
    "        # for i in range(left, mid + 1):\n",
    "        #     arr_l.append(arr[i][1])\n",
    "        # for j in range(mid + 1, right + 1):\n",
    "        #     id = bisect.bisect_left(arr_l, 2 * arr[j][1])\n",
    "        #     print(arr, arr_l, arr[j][1], id)\n",
    "        #     # if id <= mid - left and  arr_l[id] > 2 * arr[j][1]: self.count += mid - left - id + 2\n",
    "        #     if id <= mid - left and  arr_l[id] > 2 * arr[j][1]: self.count += left + mid + 1 - id\n",
    "        tmp[left:right + 1] = arr[left:right + 1]\n",
    "        # 在此之后，tmp暂存了merge之前的左右两半的数组，nums[]里边的元素经过调换（merge）之后是排序好的数组\n",
    "        i = left\n",
    "        j = mid + 1\n",
    "        while i <= mid and j <= right:\n",
    "            if arr[i][1] > 2 * arr[j][1]:      # 【易错点】arr是二维的，要取到第二个维度\n",
    "                self.count += mid - i + 1\n",
    "                j += 1\n",
    "            else:\n",
    "                i += 1\n",
    "        i = left\n",
    "        j = mid + 1\n",
    "        for p in range(left, right + 1):\n",
    "            if i == mid + 1:\n",
    "                arr[p] = tmp[j]   # 当i走到尽头的时候，把剩下的j接过来（都比i大）\n",
    "                # if tmp[i-1][1] > 2 * tmp[j][1]:   # 注意j的取值 \n",
    "                #     self.count += j - mid -1 \n",
    "                j += 1\n",
    "            elif j == right + 1:\n",
    "                arr[p] = tmp[i]\n",
    "                # if tmp[i][1] > 2 * tmp[j - 1][1]:   # 注意j的取值 \n",
    "                #     self.count += j - mid -1 \n",
    "                i += 1\n",
    "            elif tmp[i][1] <= tmp[j][1]:\n",
    "                arr[p] = tmp[i]\n",
    "                i += 1\n",
    "            elif tmp[i][1] > tmp[j][1]:\n",
    "                arr[p] = tmp[j]\n",
    "                # if tmp[i][1] > 2 * tmp[j][1]:\n",
    "                #     self.count += j - mid - 1\n",
    "                j += 1\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reversePairs(self, nums: List[int]) -> int:\n",
    "        def merge_sort(start, end):\n",
    "            if start >= end:\n",
    "                return 0   \n",
    "            mid = start + (end - start) // 2\n",
    "            count = merge_sort(start, mid) + merge_sort(mid + 1, end)\n",
    "            # 统计重要翻转对的数量\n",
    "            j = mid + 1\n",
    "            for i in range(start, mid + 1):\n",
    "                while j <= end and nums[i] > 2 * nums[j]:\n",
    "                    j += 1\n",
    "                count += (j - mid - 1)\n",
    "            \n",
    "            # 归并排序\n",
    "            temp = []\n",
    "            i, j = start, mid + 1\n",
    "            while i <= mid and j <= end:\n",
    "                if nums[i] <= nums[j]:\n",
    "                    temp.append(nums[i])\n",
    "                    i += 1\n",
    "                else:\n",
    "                    temp.append(nums[j])\n",
    "                    j += 1\n",
    "            \n",
    "            while i <= mid:\n",
    "                temp.append(nums[i])\n",
    "                i += 1\n",
    "            \n",
    "            while j <= end:\n",
    "                temp.append(nums[j])\n",
    "                j += 1\n",
    "            # 将排序好的部分复制回原数组\n",
    "            for i in range(len(temp)):\n",
    "                nums[start + i] = temp[i]\n",
    "            \n",
    "            return count\n",
    "        return merge_sort(0, len(nums) - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reversePairs(self, nums: List[int]) -> int:\n",
    "        self.cnt = 0\n",
    "        n = len(nums)\n",
    "        tmp = [0] * n\n",
    "        def sort(nums, lo, hi):\n",
    "            if lo >= hi:\n",
    "                return\n",
    "            mid = (lo + hi) // 2\n",
    "            sort(nums, lo, mid)\n",
    "            sort(nums, mid + 1, hi)\n",
    "            merge(nums, lo, mid, hi)\n",
    "\n",
    "        def merge(nums, lo, mid, hi):\n",
    "            for i in range(lo, hi+1):\n",
    "                tmp[i] = nums[i]\n",
    "            end = mid + 1\n",
    "            for i in range(lo, mid + 1):\n",
    "                while end <= hi and nums[i] > 2 * nums[end]:\n",
    "                    end += 1\n",
    "                self.cnt += end - (mid + 1)\n",
    "            i, j = lo, mid + 1\n",
    "            for p in range(lo, hi+1):\n",
    "                if i == mid + 1:\n",
    "                    nums[p] = tmp[p]\n",
    "                    j += 1\n",
    "                elif j == hi + 1:\n",
    "                    nums[p] = tmp[i]\n",
    "                    i += 1\n",
    "                elif tmp[i] <= tmp[j]:\n",
    "                    nums[p] = tmp[i]\n",
    "                    i += 1\n",
    "                else:\n",
    "                    nums[p] = tmp[j]\n",
    "                    j += 1 \n",
    "        sort(nums, 0, n-1)\n",
    "        return self.cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class BinaryIndexedTree:\n",
    "    __slots__ = [\"n\", \"c\"]\n",
    "\n",
    "    def __init__(self, n):\n",
    "        self.n = n\n",
    "        self.c = [0] * (n + 1)\n",
    "\n",
    "    def update(self, x: int, delta: int):\n",
    "        while x <= self.n:\n",
    "            self.c[x] += delta\n",
    "            x += x & -x\n",
    "\n",
    "    def query(self, x: int) -> int:\n",
    "        s = 0\n",
    "        while x > 0:\n",
    "            s += self.c[x]\n",
    "            x -= x & -x\n",
    "        return s\n",
    "\n",
    "class Solution:\n",
    "    def reversePairs(self, nums: List[int]) -> int:\n",
    "        ret = 0\n",
    "        tmp = sorted(list(map(lambda x: 2 * x, set(nums + [0]))))\n",
    "        rank = {x: i + 1 for i, x in enumerate(tmp)}\n",
    "        btree = BinaryIndexedTree(len(nums))\n",
    "        for i in range(len(nums)-1, -1, -1):\n",
    "            index = bisect_left(tmp, nums[i])\n",
    "            ret += btree.query(rank[tmp[index]] - 1)\n",
    "            btree.update(rank[2 * nums[i]], 1)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reversePairs(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        ans = [0]\n",
    "\n",
    "        def meger(l,r):\n",
    "            if l>r:return []\n",
    "            if l==r:return [nums[l]]\n",
    "            mid = (l+r)//2\n",
    "            left = meger(l,mid)\n",
    "            right = meger(mid+1,r)\n",
    "            res = []\n",
    "            m,n = len(left), len(right)\n",
    "            i,j = 0,0\n",
    "            while i<m and j<n:\n",
    "                if left[i]>=right[j]:\n",
    "                    k = bisect.bisect_right(left,2*right[j])\n",
    "                    ans[0]+=(m-k)\n",
    "                    res.append(right[j])\n",
    "                    j+=1\n",
    "                else:\n",
    "                    res.append(left[i])\n",
    "                    i+=1\n",
    "            if j<n:\n",
    "                for h in range(j,n):\n",
    "                    k = bisect.bisect_right(left,2*right[h])\n",
    "                    if m==k:break\n",
    "                    ans[0]+=(m-k)\n",
    "            res += left[i:]+right[j:]\n",
    "            return res\n",
    "        \n",
    "        meger(0,n-1)\n",
    "        return ans[0]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reversePairs(self, nums: List[int]) -> int:\n",
    "        def mergeSort(start, end):\n",
    "            if start >= end:\n",
    "                return\n",
    "            mid = (start + end) // 2\n",
    "            mergeSort(start, mid)\n",
    "            mergeSort(mid + 1, end)\n",
    "            \n",
    "            i = start\n",
    "            j = mid + 1\n",
    "            while i <= mid and j <= end:\n",
    "                if nums[i] <= 2 * nums[j]:\n",
    "                    i += 1\n",
    "                else:\n",
    "                    nonlocal count\n",
    "                    count += mid - i + 1  # 统计重要翻转对的数量\n",
    "                    j += 1\n",
    "            \n",
    "            i = start\n",
    "            j = mid + 1\n",
    "            t = start\n",
    "            while i <= mid and j <= end:\n",
    "                if nums[i] <= nums[j]:\n",
    "                    temp[t] = nums[i]\n",
    "                    i += 1\n",
    "                else:\n",
    "                    temp[t] = nums[j]\n",
    "                    j += 1\n",
    "                t += 1\n",
    "            \n",
    "            while i <= mid:\n",
    "                temp[t] = nums[i]\n",
    "                i += 1\n",
    "                t += 1\n",
    "            \n",
    "            while j <= end:\n",
    "                temp[t] = nums[j]\n",
    "                j += 1\n",
    "                t += 1\n",
    "            \n",
    "            for k in range(start, end + 1):\n",
    "                nums[k] = temp[k]\n",
    "        \n",
    "        count = 0\n",
    "        temp = [0] * len(nums)\n",
    "        mergeSort(0, len(nums) - 1)\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def reversePairs(self, nums: List[int]) -> int:\n",
    "        self.res = 0\n",
    "\n",
    "        # 归并排序 \n",
    "        def sort(arr, lo, hi):\n",
    "            if lo == hi:\n",
    "                return \n",
    "            mid = lo + (hi-lo)//2\n",
    "            sort(arr, lo, mid)\n",
    "            sort(arr, mid+1, hi)\n",
    "            merge(arr, lo, mid, hi)\n",
    "        \n",
    "        # 合并两个有序数组 arr[lo..mid] 和 arr[mid+1..hi]\n",
    "        def merge(arr, lo, mid, hi):\n",
    "            \n",
    "            # 将两个有序数组复制到 辅助数组上\n",
    "            for i in range(lo, hi+1):\n",
    "                temp[i] = arr[i]\n",
    "            \n",
    "            # 在合并有序数组之前，加点私货\n",
    "            end = mid + 1\n",
    "            for i in range(lo, mid+1):\n",
    "                # 对于左半边的每个 nums[i]，都去右半边寻找符合条件的元素\n",
    "                while end<=hi and nums[i] > 2*nums[end]:\n",
    "                    end += 1\n",
    "                \n",
    "                # 更新全局变量\n",
    "                self.res += (end - (mid+1))\n",
    "\n",
    "\n",
    "            i, j = lo, mid+1\n",
    "            for p in range(lo, hi+1):\n",
    "                if i == mid+1:\n",
    "                    # 左半边数组已全部被合并\n",
    "                    arr[p] = temp[j]\n",
    "                    j += 1\n",
    "                elif j == hi+1:\n",
    "                    # 右半边数组已全部被合并\n",
    "                    arr[p] = temp[i]\n",
    "                    i += 1\n",
    "\n",
    "                elif temp[i] > temp[j]:\n",
    "                    arr[p] = temp[j]\n",
    "                    j += 1\n",
    "                else:\n",
    "                    arr[p] = temp[i]\n",
    "                    i += 1\n",
    "\n",
    "        \n",
    "        # 归并排序要用到的辅助数组\n",
    "        temp = [None for _ in range(len(nums))]\n",
    "        \n",
    "        # 执行归并排序\n",
    "        sort(nums, 0, len(nums)-1)\n",
    "\n",
    "        return self.res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def reversePairs(self, nums: List[int]) -> int:\n",
    "        self.res = 0\n",
    "\n",
    "        # 归并排序 \n",
    "        def sort(arr, lo, hi):\n",
    "            if lo == hi:\n",
    "                return \n",
    "            mid = lo + (hi-lo)//2\n",
    "            sort(arr, lo, mid)\n",
    "            sort(arr, mid+1, hi)\n",
    "            merge(arr, lo, mid, hi)\n",
    "        \n",
    "        # 合并两个有序数组 arr[lo..mid] 和 arr[mid+1..hi]\n",
    "        def merge(arr, lo, mid, hi):\n",
    "            global res\n",
    "            \n",
    "            # 将两个有序数组复制到 辅助数组上\n",
    "            for i in range(lo, hi+1):\n",
    "                temp[i] = arr[i]\n",
    "            \n",
    "            # 在合并有序数组之前，加点私货\n",
    "            end = mid + 1\n",
    "            for i in range(lo, mid+1):\n",
    "                # 对于左半边的每个 nums[i]，都去右半边寻找符合条件的元素\n",
    "                while end<=hi and nums[i] > 2*nums[end]:\n",
    "                    end += 1\n",
    "                \n",
    "                # 更新全局变量\n",
    "                self.res += (end - (mid+1))\n",
    "\n",
    "\n",
    "            i, j = lo, mid+1\n",
    "            for p in range(lo, hi+1):\n",
    "                if i == mid+1:\n",
    "                    # 左半边数组已全部被合并\n",
    "                    arr[p] = temp[j]\n",
    "                    j += 1\n",
    "                elif j == hi+1:\n",
    "                    # 右半边数组已全部被合并\n",
    "                    arr[p] = temp[i]\n",
    "                    i += 1\n",
    "\n",
    "                elif temp[i] > temp[j]:\n",
    "                    arr[p] = temp[j]\n",
    "                    j += 1\n",
    "                else:\n",
    "                    arr[p] = temp[i]\n",
    "                    i += 1\n",
    "\n",
    "        \n",
    "        # 归并排序要用到的辅助数组\n",
    "        temp = [None for _ in range(len(nums))]\n",
    "        \n",
    "        # 执行归并排序\n",
    "        sort(nums, 0, len(nums)-1)\n",
    "\n",
    "        return self.res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reversePairs(self, nums: List[int]) -> int:\n",
    "        if len(nums)<=1:\n",
    "            return 0\n",
    "        tmp=[0]*len(nums)\n",
    "        def help(start,fin):\n",
    "            if start==fin:\n",
    "                return 0\n",
    "            l=start\n",
    "            r=fin\n",
    "            mid=(l+r)>>1\n",
    "            count=help(l,mid)+help(mid+1,r)\n",
    "            i,j=l,mid+1\n",
    "            while i<=mid or j<=r:\n",
    "                if i==mid+1:\n",
    "                    j+=1\n",
    "                elif j==r+1:\n",
    "                    i+=1\n",
    "                elif nums[i]>2*nums[j]:\n",
    "                    count+=mid-i+1\n",
    "                    j+=1\n",
    "                else:\n",
    "                    i+=1\n",
    "            i,j,pos=l,mid+1,l\n",
    "            while i<=mid or j<=r:\n",
    "                if i==mid+1:\n",
    "                    tmp[pos]=nums[j]\n",
    "                    pos+=1\n",
    "                    j+=1\n",
    "                elif j==r+1:\n",
    "                    tmp[pos]=nums[i]\n",
    "                    pos+=1\n",
    "                    i+=1\n",
    "                elif nums[i]>nums[j]:\n",
    "                    tmp[pos]=nums[j]\n",
    "                    pos+=1\n",
    "                    j+=1\n",
    "                else:\n",
    "                    tmp[pos]=nums[i]\n",
    "                    pos+=1\n",
    "                    i+=1\n",
    "            nums[l:r+1]=tmp[l:r+1]\n",
    "            return count\n",
    "        return help(0,len(nums)-1)    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reversePairs(self, nums: List[int]) -> int:\n",
    "        ans = 0\n",
    "        new_nums = [(num, idx) for idx, num in enumerate(nums)]\n",
    "\n",
    "        def divide(nums, l, r):\n",
    "            if l == r:\n",
    "                return [nums[l]]\n",
    "            m = (l + r)//2\n",
    "            left = divide(nums, l, m)\n",
    "            right = divide(nums, m+1, r)\n",
    "            isReversePairs(left, right)\n",
    "            # print(ans)\n",
    "            return merge(left, right)\n",
    "        \n",
    "        def isReversePairs(left, right):\n",
    "            nonlocal ans\n",
    "            lp, rp, m, n = 0, 0, len(left), len(right)\n",
    "            while lp < m:\n",
    "                while rp < n and left[lp][0] <= 2*right[rp][0]:\n",
    "                    rp += 1\n",
    "                ans += n - rp\n",
    "                if rp == n:\n",
    "                    break\n",
    "                lp += 1\n",
    "        \n",
    "        def merge(left, right):\n",
    "            lp, rp, m, n = 0, 0, len(left), len(right)\n",
    "            ret = []\n",
    "\n",
    "            while lp < m and rp < n:\n",
    "                l_value, l_idx = left[lp]\n",
    "                r_value, r_idx = right[rp]     \n",
    "                if l_value > r_value:\n",
    "                    ret.append((l_value, l_idx))\n",
    "                    lp += 1\n",
    "                else:\n",
    "                    ret.append((r_value, r_idx))\n",
    "                    rp += 1\n",
    "            \n",
    "            while lp < m:\n",
    "                l_value, l_idx = left[lp]\n",
    "                ret.append((l_value, l_idx))\n",
    "                lp += 1\n",
    "            \n",
    "            while rp < n:\n",
    "                r_value, r_idx = right[rp]\n",
    "                ret.append((r_value, r_idx))\n",
    "                rp += 1\n",
    "            # print(ret)\n",
    "            return ret\n",
    "        \n",
    "        divide(new_nums, 0, len(nums)-1)\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reversePairs(self, nums: List[int]) -> int:\n",
    "        l = []\n",
    "        for i, num in enumerate(nums):\n",
    "            l.append((2 * num, i))\n",
    "        l.sort()\n",
    "        n = len(nums)\n",
    "        new_l = []\n",
    "\n",
    "        index_map = {}\n",
    "        for t in l:\n",
    "            if len(new_l) == 0 or new_l[-1] != t[0]:\n",
    "                new_l.append(t[0])\n",
    "            index_map[t[1]] = len(new_l) - 1\n",
    "        # print(new_l)\n",
    "        i = n - 1\n",
    "        count = 0\n",
    "        tree = [0] * (4 * len(new_l))\n",
    "        while i >= 0:\n",
    "            num = nums[i]\n",
    "            query_index = bisect.bisect_left(new_l, num) - 1\n",
    "            if query_index >= 0:\n",
    "                count += self.query(tree, 0, query_index, 0, 0, len(new_l) - 1)\n",
    "            # print(tree)\n",
    "            update_index = index_map[i]\n",
    "            self.update(tree, update_index, 0, 0, len(new_l) - 1)\n",
    "            i -= 1\n",
    "\n",
    "        return count\n",
    "\n",
    "\n",
    "    def update(self, tree, update_index, index, left, right):\n",
    "        if left == right:\n",
    "            tree[index] += 1\n",
    "            return\n",
    "        else:\n",
    "            mid = (left + right) // 2\n",
    "            if update_index <= mid:\n",
    "                self.update(tree, update_index, 2 * index + 1, left, mid)\n",
    "            else:\n",
    "                self.update(tree, update_index, 2 * index + 2, mid + 1, right)\n",
    "            tree[index] += 1\n",
    "            return\n",
    "\n",
    "    def query(self, tree, left_index, right_index, index, left, right):\n",
    "        if left == right:\n",
    "            return tree[index]\n",
    "        elif left == left_index and right == right_index:\n",
    "            return tree[index]\n",
    "        else:\n",
    "            mid = (left + right) // 2\n",
    "            if right_index <= mid:\n",
    "                return self.query(tree, left_index, right_index, 2 * index + 1, left, mid)\n",
    "            elif mid + 1 <= left_index:\n",
    "                return self.query(tree, left_index, right_index, 2 * index + 2, mid + 1, right)\n",
    "            else:\n",
    "                return self.query(tree, left_index, mid, 2 * index + 1, left, mid) + self.query(tree, mid + 1, right_index, 2 * index + 2, mid + 1, right)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reversePairs(self, nums: List[int]) -> int:\n",
    "        temp = [0] * len(nums)\n",
    "\n",
    "        def merge_sort(lo, hi):\n",
    "            if lo >= hi: return 0\n",
    "\n",
    "            mid = lo + (hi - lo) // 2\n",
    "            count = merge_sort(lo, mid) + merge_sort(mid + 1, hi)\n",
    "\n",
    "            for i in range(lo, hi + 1):\n",
    "                temp[i] = nums[i]\n",
    "\n",
    "            def count_or_merge(is_count, count=count):\n",
    "\n",
    "                i, j, k = lo, mid + 1, lo\n",
    "                while i <= mid or j <= hi:\n",
    "                    left = temp[i] if i <= mid else float('inf')\n",
    "                    right = temp[j] * (is_count + 1) if j <= hi else float('inf')\n",
    "                    if left <= right:\n",
    "                        if is_count:\n",
    "                            count += j - mid - 1\n",
    "                        else:\n",
    "                            nums[k] = left\n",
    "                        i += 1\n",
    "                    else:\n",
    "                        if not is_count:\n",
    "                            nums[k] = right\n",
    "                        j += 1\n",
    "                    k += 1\n",
    "                return count\n",
    "            \n",
    "            count = count_or_merge(True)\n",
    "            count_or_merge(False)\n",
    "            \n",
    "            return count\n",
    "        \n",
    "        return merge_sort(0, len(nums) - 1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class SegmenrTree:\r\n",
    "    def lowbit(self,x):\r\n",
    "        return x & -x\r\n",
    "    def __init__(self,nums):\r\n",
    "        self.n=len(nums)\r\n",
    "        self.tree=[0]+nums\r\n",
    "        for i in range(1,self.n+1):\r\n",
    "            j=self.lowbit(i)+i\r\n",
    "            if j<self.n+1:\r\n",
    "                self.tree[j]+=self.tree[i]\r\n",
    "    def add(self,index,val):\r\n",
    "        i=index+1\r\n",
    "        while(i<self.n+1):\r\n",
    "            self.tree[i]+=val\r\n",
    "            i=i+self.lowbit(i)\r\n",
    "    def preSum(self,index):\r\n",
    "        i=index+1\r\n",
    "        summ=0\r\n",
    "        while(i>0):\r\n",
    "            summ+=self.tree[i]\r\n",
    "            i=i-self.lowbit(i)\r\n",
    "        return summ\r\n",
    "        \r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def reversePairs(self, nums: List[int]) -> int:\r\n",
    "        halfN=list(set([x for x in nums]))+list(set([(x-1)//2 for x in nums]))\r\n",
    "        halfN.sort()\r\n",
    "        halfD={v:i for i,v in enumerate(halfN)}\r\n",
    "\r\n",
    "        hums=[0]*len(halfN)\r\n",
    "        st=SegmenrTree(hums)\r\n",
    "        summ=0\r\n",
    "        for i in range(len(nums)-1,-1,-1):\r\n",
    "            tmp=nums[i]\r\n",
    "            summ+=st.preSum(halfD[(tmp-1)//2])\r\n",
    "            st.add(halfD[tmp],1)\r\n",
    "        return summ\r\n",
    "        # summ=0\r\n",
    "        # for i in range(len(nums)-2,-1,-1):\r\n",
    "        #     tmp=nums[i]\r\n",
    "        #     s=sum([1 if 2*j<tmp else 0 for j in nums[i+1:]])\r\n",
    "        #     summ+=s\r\n",
    "        # return summ\r\n",
    "\r\n",
    "\r\n",
    "\r\n",
    "        \r\n",
    "\r\n",
    "\r\n",
    "            \r\n",
    "\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def reversePairs(self, nums: List[int]) -> int:\n",
    "        values = {}\n",
    "        for num in nums:\n",
    "            values[num] = None\n",
    "            values[num * 2] = None\n",
    "        index = 1\n",
    "        for num in (sorted(values.keys())):\n",
    "            values[num] = index\n",
    "            index += 1\n",
    "\n",
    "        ans = 0\n",
    "        length = len(values)\n",
    "        bit_tree = BitTree(length)\n",
    "        total_count = 0\n",
    "        for num in nums:\n",
    "            ans += total_count - bit_tree.get_count(values[2 * num])\n",
    "            total_count += 1\n",
    "            bit_tree.update_index(values[num])\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n",
    "class BitTree:\n",
    "    def __init__(self, l):\n",
    "        self.__values = [0] * (l + 1)\n",
    "        self.__l = l\n",
    "\n",
    "    def update_index(self, index):\n",
    "        while index <= self.__l:\n",
    "            self.__values[index] += 1\n",
    "            index += self.__low_bit(index)\n",
    "\n",
    "    def get_count(self, index):\n",
    "        rtn = 0\n",
    "        while index > 0:\n",
    "            rtn += self.__values[index]\n",
    "            index -= self.__low_bit(index)\n",
    "\n",
    "        return rtn\n",
    "\n",
    "    def __low_bit(self, index):\n",
    "        return index & (-index)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class BIT:\n",
    "    def __init__(self, n):\n",
    "        self.tree = [0]*n\n",
    "    \n",
    "    def add(self, i, delta):\n",
    "        while i<len(self.tree):\n",
    "            self.tree[i] += delta\n",
    "            i += i&-i\n",
    "    \n",
    "    def query(self, i):\n",
    "        res = 0\n",
    "        while i>0:\n",
    "            res += self.tree[i]\n",
    "            i -= i&-i\n",
    "        return res\n",
    "\n",
    "class Solution:\n",
    "    def reversePairs(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        a = nums+[x/2 for x in nums]\n",
    "        rank_map = {x: i+1 for i, x in enumerate(sorted(set(a)))}\n",
    "        t = BIT(len(rank_map)+1)\n",
    "        res = 0\n",
    "        for x in nums[::-1]:\n",
    "            rank_i = rank_map[x]\n",
    "            rank_j = rank_map[x/2]\n",
    "            res += t.query(rank_j-1)\n",
    "            t.add(rank_i, 1)\n",
    "        return res\n",
    "\n",
    "        # from sortedcontainers import SortedList\n",
    "        # sl = SortedList()\n",
    "        # n = len(nums)\n",
    "        # res = 0\n",
    "        # for i in range(n-1, -1, -1):\n",
    "        #     x = nums[i]\n",
    "        #     res += sl.bisect_left(x/2)\n",
    "        #     sl.add(x)\n",
    "        # return res\n",
    "\n",
    "        # n = len(nums)\n",
    "        # a = nums+[2*x for x in nums]\n",
    "        # rank_map = {x: i+1 for i, x in enumerate(sorted(set(a)))}\n",
    "        # t = BIT(len(rank_map)+1)\n",
    "        # res = 0\n",
    "        # for j, x in enumerate(nums):\n",
    "        #     rank_i = rank_map[2*x]\n",
    "        #     res += t.query(len(rank_map))-t.query(rank_i)\n",
    "        #     rank_j = rank_map[x]\n",
    "        #     t.add(rank_j, 1)\n",
    "        # return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 树状数组\n",
    "class BIT:\n",
    "    # 长度为 n 的初始值为 0 的树状数组\n",
    "    def __init__(self, n):\n",
    "        self.n = n \n",
    "        self.tree = [0] * (n+1)\n",
    "\n",
    "    # 单点修改操作\n",
    "    def update(self, x, k):\n",
    "        while x <= self.n:\n",
    "            self.tree[x] += k  # 将区间 [(x-lowbit(x)), x] 上所有结点加上 k \n",
    "            x += self.lowbit(x)  # 往前跳 lowbit(x)\n",
    "\n",
    "    # 区间查询操作(1 到 x 的区间和)\n",
    "    def query(self, x):\n",
    "        res = 0\n",
    "        while x > 0:\n",
    "            res += self.tree[x]  # 累加区间 [(x-lowbit(x)), x] 上所有结点的值\n",
    "            x -= self.lowbit(x)  # 往后跳 lowbit(x)\n",
    "        return res \n",
    "\n",
    "    # lowbit: 返回 x 的最低位1所对应的值(这里用二进制表示)\n",
    "    def lowbit(self, x):\n",
    "        return x & -x\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def reversePairs(self, nums: List[int]) -> int:\n",
    "        t = []\n",
    "        for num in nums:\n",
    "            t.append(num)\n",
    "            t.append(num*2)\n",
    "        # 映射到 1~n+1\n",
    "        t.sort()\n",
    "        n = len(t)\n",
    "        d = dict(zip(t, range(1, n+1)))\n",
    "        res = 0\n",
    "        bit = BIT(n+1)\n",
    "        for num in nums:\n",
    "            res += bit.query(n) - bit.query(d[2*num])\n",
    "            bit.update(d[num], 1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class BIT(): # 1-indexed\n",
    "    def __init__(self, n):\n",
    "        self.n = n\n",
    "        self.tree = [0] * (n + 1)\n",
    "    \n",
    "    def add(self, i, inc):\n",
    "        while i <= self.n:\n",
    "            self.tree[i] += inc\n",
    "            i += i & (-i)\n",
    "\n",
    "    def getsum(self, l, r): # sum over [l,...,r]\n",
    "        return self._getsum(r) - self._getsum(l - 1)\n",
    "\n",
    "    def _getsum(self, i): #sum over [1,...,i]\n",
    "        ans = 0\n",
    "        while i > 0:\n",
    "            ans += self.tree[i]\n",
    "            i -= i & (-i)\n",
    "        return ans\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def reversePairs(self, nums: List[int]) -> int:\n",
    "        M = [-2**31, 2**31-1]\n",
    "        x = [(v+1)//2-1 for v in itertools.chain(M, nums)]\n",
    "        x = sorted(set(itertools.chain(x, nums, M)))\n",
    "        x2i = {v:i+1 for i,v in enumerate(x)}\n",
    "        t = BIT(len(x))\n",
    "        n = len(x)\n",
    "        ans = 0\n",
    "        for v in nums:\n",
    "            ans += t.getsum(x2i[v], n)\n",
    "            t.add(x2i[(v+1)//2-1], 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class treeArray:\n",
    "    def __init__(self, n):\n",
    "        self.tree = [0] * (n + 1)\n",
    "    \n",
    "    def update(self, i, val):\n",
    "        # 原数组的i加上val\n",
    "        i += 1\n",
    "        while i < len(self.tree):\n",
    "            self.tree[i] += val\n",
    "            i += i & -i\n",
    "    \n",
    "    def getSum(self, i):\n",
    "        # 返回原数组0~n-1\n",
    "        ans = 0\n",
    "        while i:\n",
    "            ans += self.tree[i]\n",
    "            i -= i & -i\n",
    "        return ans\n",
    "\n",
    "class Solution:\n",
    "    def reversePairs(self, nums: List[int]) -> int:\n",
    "        # SortedList做法：从末尾挨个把元素加进去。 O(nlogn)        \n",
    "        # 树状数组: 要离散化 num, num*2\n",
    "\n",
    "        candidates = set()\n",
    "        for num in nums:\n",
    "            candidates.update([num, num * 2])\n",
    "        \n",
    "        candidates = list(candidates)\n",
    "        candidates.sort()\n",
    "\n",
    "        # 离散化\n",
    "        valid_id = dict()\n",
    "        for i, c in enumerate(candidates):\n",
    "            valid_id[c] = i\n",
    "        \n",
    "        treearr = treeArray(len(candidates))\n",
    "\n",
    "        ans = 0\n",
    "        for num in nums[::-1]:\n",
    "            idx = valid_id[num]\n",
    "            ans += treearr.getSum(idx)\n",
    "            treearr.update(valid_id[num*2], 1)\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reversePairs(self, nums: List[int]) -> int:\n",
    "        if not nums:\n",
    "            return 0\n",
    "\n",
    "        mp = {}\n",
    "        for index, x in enumerate(sorted(nums + [2*y for y in nums]), start=1):\n",
    "            mp[x] = index\n",
    "        bit = Bit(index)\n",
    "\n",
    "        ans = 0\n",
    "        for j, nj in enumerate(nums):\n",
    "            nj2 = mp[nj*2]\n",
    "            nj = mp[nj]\n",
    "            ans += j - bit.query(nj2) # 总数 == index + 1\n",
    "            bit.add(nj, 1)\n",
    "        return ans     \n",
    "\n",
    "class Bit:\n",
    "    def __init__(self,n):\n",
    "        self.tree = [0] * (n+1)\n",
    "        self.n = n\n",
    "    \n",
    "    @staticmethod\n",
    "    def lowbit(x):\n",
    "        return x & -x\n",
    "    \n",
    "    def add(self, i, v):\n",
    "        while i <= self.n:\n",
    "            self.tree[i] += v\n",
    "            i += self.lowbit(i)\n",
    "\n",
    "    def query(self, i):\n",
    "        s = 0\n",
    "        while i > 0:\n",
    "            s += self.tree[i]\n",
    "            i -= self.lowbit(i)\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from math import inf\n",
    "from collections import defaultdict\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def reversePairs(self, nums: List[int]) -> List[int]:\n",
    "        og_nums = nums[:]\n",
    "        nums += [v*2 for v in nums]\n",
    "        tmp = {v:i for i, v in enumerate(sorted(nums), start=1)}\n",
    "        nums = [tmp[v] for v in nums]\n",
    "        tree = [0] * (len(nums)+1)\n",
    "        N = len(nums)\n",
    "\n",
    "        def query(n):\n",
    "            res = 0\n",
    "            while n:\n",
    "                res += tree[n]\n",
    "                n = n & (n-1)\n",
    "            return res\n",
    "\n",
    "        def update(n):\n",
    "            while n < len(tree):\n",
    "                tree[n] += 1\n",
    "                n += n & -n\n",
    "        \n",
    "        cnt = 0\n",
    "        for i, oc in enumerate(og_nums, start=1):\n",
    "            c = tmp[oc*2]\n",
    "            #print(f'{oc=} {tmp[oc]} {c=} %d %s' % (query(N-1), query(c)))\n",
    "            cnt += query(N) - query(c)\n",
    "            update(tmp[oc])\n",
    "        return cnt\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import numpy as np\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def sort(self, nums):\n",
    "        self.temp = [0] * len(nums)\n",
    "        self._sort(nums, 0, len(nums) - 1)\n",
    "\n",
    "    def _sort(self, nums, lo, hi):\n",
    "        if lo >= hi:\n",
    "            return\n",
    "        # partition\n",
    "        mid = lo + (hi - lo) // 2 # 防止整型溢出\n",
    "        self._sort(nums, lo, mid)\n",
    "        self._sort(nums, mid + 1, hi)\n",
    "        self._merge(nums, lo, mid, hi)\n",
    "\n",
    "    def _merge(self, nums, lo, mid, hi):\n",
    "        # 保存排好序但是还没有合并的数据到temp\n",
    "        for i in range(lo, hi + 1):\n",
    "            self.temp[i] = nums[i]\n",
    "        # 合并前统计反转对\n",
    "        end = mid + 1\n",
    "        for i in range(lo, mid+1):\n",
    "            while end <= hi and nums[i] > 2 * nums[end]:\n",
    "                end += 1\n",
    "            self.cnt += end - (mid + 1)\n",
    "        # 双指针合并数组\n",
    "        i = lo\n",
    "        j = mid + 1\n",
    "        for p in range(lo, hi + 1):\n",
    "            if i == mid + 1:\n",
    "                nums[p] = self.temp[j]\n",
    "                j += 1\n",
    "            elif j == hi + 1:\n",
    "                nums[p] = self.temp[i]\n",
    "                i += 1\n",
    "            elif self.temp[i] > self.temp[j]:\n",
    "                nums[p] = self.temp[j]\n",
    "                j += 1\n",
    "            else:\n",
    "                nums[p] = self.temp[i]\n",
    "                i += 1\n",
    "        \n",
    "    def reversePairs(self, nums: List[int]) -> int:\n",
    "        self.cnt = 0\n",
    "        self.sort(nums)\n",
    "        return self.cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def reversePairs(self, nums: List[int]) -> int:\n",
    "        t = nums.copy()\n",
    "        nums.sort()\n",
    "        maps = {}\n",
    "        maxV = nums[0]\n",
    "        for i in nums:\n",
    "            maxV = max(maxV,i)\n",
    "            if i in maps:\n",
    "                maps[i]+= 1\n",
    "            else:\n",
    "                maps[i] = 1\n",
    "\n",
    "\n",
    "        def find(start,end,x):\n",
    "            if start+1 >= end:\n",
    "                if nums[start]>=x:\n",
    "                    return nums[start]\n",
    "                return nums[end]\n",
    "            else:\n",
    "                mid = (start + end)//2\n",
    "                if nums[mid]==x:\n",
    "                    return nums[mid]\n",
    "                elif nums[mid]>x:\n",
    "                    end = mid\n",
    "                else:\n",
    "                    start = mid\n",
    "            return find(start,end,x)\n",
    "        s = t.copy()\n",
    "        s.reverse()\n",
    "\n",
    "        array = []\n",
    "        dicts = {}\n",
    "        count = 0\n",
    "        for i in maps:\n",
    "            dicts[i] = count\n",
    "            array.append(maps[i])\n",
    "            count+=1\n",
    "        def lowbot(x):\n",
    "            return x & -x\n",
    "\n",
    "        t = [0] * (len(array)+1)\n",
    "\n",
    "        for i in range(len(array)):\n",
    "            x = i+1\n",
    "            t[x] = sum(array[x-lowbot(x):x])\n",
    "\n",
    "        def update(x,k):\n",
    "            while x <= len(t)-1 and x:\n",
    "                t[x] += k\n",
    "                x += lowbot(x)\n",
    "\n",
    "        def ask(x):  \n",
    "            ans = t[x]\n",
    "            while x:\n",
    "                x = x-lowbot(x)\n",
    "                ans += t[x]\n",
    "            return ans\n",
    "\n",
    "\n",
    "        ans = 0\n",
    "        for i in s:\n",
    "            maps[i]-=1\n",
    "            update(dicts[i]+1,-1)\n",
    "            if i*2+1<=maxV:\n",
    "                idx = find(0,len(nums),i*2+1)\n",
    "                ans += (ask(len(t)-1) - ask(dicts[idx]))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self, start, end):\n",
    "        self.start = start                                                                              \n",
    "        self.end = end\n",
    "        self.sum = 0                                                                                    \n",
    "        self.left_child = None                                                                          \n",
    "        self.right_child = None\n",
    "\n",
    "class SegmentTree:                                 \n",
    "    def __init__(self, nums):\n",
    "        self.root = self.build_tree(nums, 0, len(nums)-1)\n",
    "                    \n",
    "    def build_tree(self, nums, start, end):\n",
    "        if start > end:                                                                                 \n",
    "            return None\n",
    "               \n",
    "        node = Node(start, end)                    \n",
    "        if start == end:\n",
    "            node.sum = nums[start]\n",
    "        else:\n",
    "            mid = (start + end) // 2\n",
    "            node.left_child = self.build_tree(nums, start, mid)\n",
    "            node.right_child = self.build_tree(nums, mid+1, end)\n",
    "            node.sum = node.left_child.sum + node.right_child.sum\n",
    "                        \n",
    "        return node                                                                                                                                                                                             \n",
    "                                                                                                        \n",
    "    def update(self, node, index, val):           \n",
    "        if node.start == node.end:\n",
    "            node.sum += val\n",
    "        else:\n",
    "            mid = (node.start + node.end) // 2\n",
    "            if index <= mid:                                                                                                                                                                                    \n",
    "                self.update(node.left_child, index, val)\n",
    "            else:      \n",
    "                self.update(node.right_child, index, val)\n",
    "            node.sum = node.left_child.sum + node.right_child.sum\n",
    "     \n",
    "    def query(self, node, start, end):\n",
    "        if start <= node.start and end >= node.end:\n",
    "            return node.sum\n",
    "        elif start > node.end or end < node.start:\n",
    "            return 0\n",
    "        else:\n",
    "            return self.query(node.left_child, start, end) + self.query(node.right_child, start, end)\n",
    "\n",
    "class Solution:\n",
    "    def reversePairs(self, nums: List[int]) -> int:\n",
    "        if not nums:\n",
    "            return 0\n",
    "         \n",
    "        sorted_nums = sorted(nums)\n",
    "        seg_tree = SegmentTree([0] * len(nums))\n",
    "        res = 0\n",
    "         \n",
    "        for num in nums:\n",
    "            res += seg_tree.query(seg_tree.root, bisect.bisect_right(sorted_nums, 2*num), len(sorted_nums)-1)\n",
    "            idx = bisect.bisect_left(sorted_nums, num)\n",
    "            seg_tree.update(seg_tree.root, idx, 1)\n",
    "         \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Bit:\n",
    "    def __init__(self, n):\n",
    "        self.tree = [0] * (n + 1)\n",
    "        self.n = n\n",
    "\n",
    "    def update(self, index, diff):\n",
    "        index += 1\n",
    "        while index <= self.n:\n",
    "            self.tree[index] += diff\n",
    "            index += index&(-index)\n",
    "\n",
    "    def query(self, index):\n",
    "        index += 1\n",
    "        acc = 0\n",
    "        while index >= 1:\n",
    "            acc += self.tree[index]\n",
    "            index -= index&(-index)\n",
    "        return acc\n",
    "\n",
    "class Solution:\n",
    "    def reversePairs(self, nums: List[int]) -> int:\n",
    "        \n",
    "        numSet = set(nums) | set(2*num for num in nums)\n",
    "        num2Idx = {num: i for i, num in enumerate(sorted(numSet))}\n",
    "        bit = Bit(len(numSet))\n",
    "        ans = 0\n",
    "\n",
    "        for i in range(len(nums)-1,-1,-1):\n",
    "            ans += bit.query(num2Idx[nums[i]]-1)\n",
    "            bit.update(num2Idx[2*nums[i]], 1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class TreeArr:\n",
    "    def __init__(self,n):\n",
    "        self.n = n\n",
    "        self.tree = [0]*(n+1)\n",
    "    \n",
    "    def lowbit(self,x):\n",
    "        return x&-x\n",
    "\n",
    "    def query(self,x):\n",
    "        ans = 0\n",
    "        while x!=0:\n",
    "            ans+=self.tree[x]\n",
    "            x -= self.lowbit(x)\n",
    "        return ans\n",
    "\n",
    "    def update(self,x,d):\n",
    "        while x<=self.n:\n",
    "            self.tree[x]+=d\n",
    "            x+=self.lowbit(x)\n",
    "\n",
    "from sortedcontainers import SortedDict\n",
    "class Solution:\n",
    "    def reversePairs(self, nums: List[int]) -> int:\n",
    "        allNums = SortedDict()\n",
    "        for num in nums:\n",
    "            allNums[num] = True\n",
    "            allNums[2*num] = True\n",
    "\n",
    "        values = {}\n",
    "        idx = 0\n",
    "        for x in allNums.keys():\n",
    "            values[x] = idx\n",
    "            idx+=1\n",
    "        \n",
    "        res = 0\n",
    "        BIT = TreeArr(len(values))\n",
    "        for i in range(len(nums)):\n",
    "            left = values[nums[i]*2]\n",
    "            right = len(values)-1\n",
    "            res+=BIT.query(right+1)-BIT.query(left+1)\n",
    "            BIT.update(values[nums[i]]+1,1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class BinaryIndexedTree:\n",
    "    def __init__(self, length):\n",
    "        self.n = length\n",
    "        self.c = [0]* (length+1)\n",
    "    def lowbit(self,x):\n",
    "        return x & (-x)\n",
    "    def update(self, pos):\n",
    "        while pos <= self.n:\n",
    "            self.c[pos] += 1\n",
    "            pos += self.lowbit(pos)\n",
    "    def query(self, pos):\n",
    "        ans = 0\n",
    "        while pos > 0:\n",
    "            ans += self.c[pos]\n",
    "            pos -= self.lowbit(pos)\n",
    "        return ans\n",
    "class Solution:\n",
    "    def reversePairs(self, nums: List[int]) -> int:\n",
    "        ##线段树\n",
    "        a = set()\n",
    "        for x in nums:\n",
    "            a.add(x)\n",
    "            a.add(2*x)\n",
    "        vaule2Id = {v:i for i,v in enumerate(sorted(a)) }\n",
    "        tree = BinaryIndexedTree(len(vaule2Id))\n",
    "        ans = 0\n",
    "        for i in range(len(nums)):\n",
    "            left = vaule2Id[2*nums[i]]\n",
    "            right = len(a)-1\n",
    "            ans += tree.query(right+1) - tree.query(left+1)\n",
    "            tree.update(vaule2Id.get(nums[i])+1)\n",
    "        return ans\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
